Division Algorithm
Module 02 / Lesson 01
Visual Explanation
The Foundation of Modulo Math
The Division Algorithm is a fundamental theorem in mathematics. It states that for any two integers a (dividend) and n (divisor), there exist unique integers q (quotient) and r (remainder).
a = n × q + r
Condition: 0 ≤ r < n
Key Components:
- Dividend (a): The number being divided
- Divisor (n): The number we divide by
- Quotient (q): How many times n goes into a
- Remainder (r): What's left over
Key Rules:
- Remainder must be non-negative (r ≥ 0)
- Remainder must be less than divisor (r < n)
- Solution must be unique
Python Implementation
Python handles negative division correctly to ensure a positive remainder:
def division_algorithm(a, n):
# Calculate quotient using floor division
q = a // n
# Calculate remainder using modulo
r = a % n
return q, r
# Example 1: a = 17, n = 5
q1, r1 = division_algorithm(17, 5)
print(f"17 = 5({q1}) + {r1}") # Output: 17 = 5(3) + 2
# Example 2: a = -13, n = 4
q2, r2 = division_algorithm(-13, 4)
print(f" -13 = 4({q2}) + {r2}") # Output: -13 = 4(-4) + 3